home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 6_10.lha / 6_10 / 6_10mul.c < prev    next >
Text File  |  1993-08-08  |  2KB  |  124 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. *
  6.    Multiply u[1..n] * v[1..m] to form w[0..m+n]
  7.  
  8.    Based on:
  9.  
  10.    The Art of Computer Programming, volume 2
  11.    D. Knuth, Section 4.3.1, Algorithm M
  12.  
  13.    modified to ignore w[0..m]
  14. /
  15. include <lint.h>
  16.  
  17. INT operator*(LINT u, LINT v)
  18.  
  19.    int negans = 0;
  20.  
  21.    /*
  22. Make u positive
  23.    */
  24.    if (u.isneg())
  25. {
  26. negans = 1;
  27. u = -u;
  28. }
  29.  
  30.    /*
  31. Make v positive
  32.    */
  33.    if (v.isneg())
  34. {
  35. negans = 1 - negans;
  36. v = -v;
  37. }
  38.  
  39.    /*
  40. M1(a) [Initialize]
  41.     Set w[m+1..m+n] <- 0
  42. { modified: set w[0..n] <- 0 }
  43.    */
  44.    LINT w = 0;
  45.  
  46.    /*
  47. M1(b) [Initialize]
  48.     Set j <- m
  49. M6 [Loop on j]
  50.     decrease j by one
  51.     if j > 0, goto M2
  52.    */
  53.    for (int j = 3; j >= 0; j--)
  54. {
  55. /*
  56.     M2 [zero multiplier?]
  57.     if v[j] == 0
  58.         w[j] <- 0
  59.         goto M6
  60.     { modified: skip w[j] since 0<=j<m }
  61. */
  62. if (v.s[j] == 0)
  63.     ;
  64.     // w.s[j] = 0;
  65.  
  66. else
  67.     {
  68.     /*
  69.     M3 [Initialize i]
  70.         set i <- n,
  71.         k <- 0
  72.     M5(a) [Loop on i]
  73.         decrease i by one
  74.         if i > 0, goto M4
  75.     { modified: loop on i+j > 0, i+j<n }
  76.     */
  77.  
  78.     LINT_Ltype v_j = v.s[j];
  79.     for (int i = 3, k = 0, iplusj = i + j - 3;
  80.      iplusj >= 0;
  81.      i--, iplusj--)
  82.     {
  83.     /*
  84.         M4 [multiply and add]
  85.         Set t <- u[i] * v[j] + w[i+j] + k
  86.             w[i+j] <- t % b
  87.             k <- t / b
  88.         { modified: i+j tracks i }
  89.     */
  90.  
  91.     LINT_Ltype t = u.s[i] * v_j +
  92.         w.s[iplusj] + k;
  93.     w.s[iplusj] = t;    // % LINT_base
  94.     k = t / LINT_base;
  95.     }
  96.  
  97.     /*
  98.     M5(b) [Loop on i]
  99.         if i <= 0,
  100.         set w[j] <- k
  101.     { modified: skip setting w[j],
  102.       since j<m }
  103.     */
  104.     // w.s[j] = k;
  105.     }
  106. }
  107.  
  108.    /*
  109. set prod <- w[m+1..m+n]
  110. { modified: set prod <- w[1..n] }
  111.    */
  112.    LINT prod;
  113.    for (int i = 0; i < 4; i++)
  114. prod.s[i] = w.s[i];
  115.  
  116.    /*
  117. restore sign
  118.    */
  119.    if (negans)
  120. return -prod;
  121.    else
  122. return prod;
  123.  
  124.